package linear.linked.single;

import java.util.Iterator;

/**
 * 单链表
 * @author caasi
 * @since 2022-01-14 10:53:23
 */
public class SingleLInkedList<T> implements Iterable<T>{
    
    //头结点
    private Node<T> head;
    
    //链表长度
    private int size;

    //构造方法
    public SingleLInkedList() {
        this.size = 0;
        this.head = new Node<>(null, null);
    }

    //清空链表
    public void clear() {
        head.next = null;
        size = 0;
    }

    //判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //链表的长度
    public int size() {
        return size;
    }

    //返回下标为i的元素
    public T get(int index) {
        checkIndexSafe(index);
        Node<T> node = node(index);
        return node.value;
    }

    //向链表末尾添加元素
    public void insert(T t) {
        Node<T> newNode = new Node<>(t, null);
        Node<T> node = node(size - 1);
        node.next = newNode;
        size++;
    }

    //向链表下标为i的元素之前添加元素
    public void insert(T t, int index) {
        checkIndexSafe(index);
        Node<T> node = node(index - 1);
        Node<T> next = node.next;
        node.next = new Node<>(t, next);
        size++;
    }

    //删除下标为i的元素并返回
    public T remove(int index) {
        checkIndexSafe(index);
        //找到下标为i的节点前面的一个节点
        Node<T> node = node(index - 1);
        Node<T> remove = node.next;
        Node<T> next = remove.next;
        node.next = next;
        size--;
        return remove.value;
    }

    //返回链表中首次出现的元素t的下标，如果没有t元素，则返回-1
    public int indexOf(T t) {
        Node<T> node = head;
        int index = -1;
        while (node.next != null) {
            node = node.next;
            index++;
            if (node.value.equals(t))
                return index;
        }
        return -1;
    }

    //反转链表-就地逆置
    public void reverse() {
        //第一个元素也是反转后的最后一个元素
        Node<T> begin = head.next;
        //为空说明无数据直接return
        if (begin == null) return;
        //第一个元素的下一个元素，由此开始
        Node<T> end = begin.next;
        while (end != null) {
            //end不为空则删除end 使第一个元素的指向end的下一个
            begin.next = end.next;
            //在头部插入end
            end.next = head.next;
            head.next = end;
            //end指向第一个元素的下一个元素 重复上述步骤直到最后一个元素
            end = begin.next;
        }
    }

    //反转链表-递归
    public void reverseRecursive() {
        reverseRecursion(head.next);
    }

    //反转链表-递归
    public Node<T> reverseRecursion(Node<T> current) {
        //如果条件成立，说明已经到了链表的最后一个元素 即反转后的链表的第一个元素 将head.next指向它
        if (current == null || current.next == null) {
            head.next = current;
            return current;
        } else {
            //不成立则继续递归
            Node<T> next = reverseRecursion(current.next);
            //假设链表为1,2,3,4
            //最后一层递归退出条件，返回的节点为节点4，next = 4，current为节点3，此时交换节点的指向由3->4指向4->3，并将节点3的指向置空
            //并且返回节点3给节点2(节点3递归退出进入节点2 reverseRecursion调用后的代码)
            next.next = current;
            current.next = null;
            return current;
        }
    }
    
    //快慢指针查找中间值
    public T getMidValue() {
        if (isEmpty()) return null;
        Node<T> fast = head.next;
        Node<T> slow = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow.value;
    }
    
    //查找下标为i的节点
    private Node<T> node(int index) {
        int i = 0;
        Node<T> node = head;
        while (i <= index) {
            node = node.next;
            i++;
        }
        return node;
    }

    //检查下标是否安全
    private void checkIndexSafe(int index) {
        if (index >= size || index < 0)
            throw new IndexOutOfBoundsException();
    }

    //迭代器
    @Override
    public Iterator<T> iterator() {
        return new SingleLinkedListIterator();
    }
    
    //迭代器内部类
    private class SingleLinkedListIterator implements Iterator<T>{
        
        private Node<T> current;
        
        public SingleLinkedListIterator(){
            this.current = head;
        }
        
        @Override
        public boolean hasNext() {
            return current.next != null;
        }

        @Override
        public T next() {
            current = current.next;
            return current.value;
        }
    }

    //节点内部类
    private class Node<T> {
        
        //值域
        private T value;
        
        //指针域
        private Node<T> next;

        //构造方法
        public Node(T value, Node<T> next) {
            this.value = value;
            this.next = next;
        }

    }
    
}
